Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
Комп’ютерна схемотехніка та архітектура комп’ютерів
ЗВІТ
ДО ЛАБОРАТОРНОЇ РОБОТИ № 2
«Синтез перемикальних функцій»
Варіант № 7
Дата «4» Жовтня 2021
Мета роботи: Закріплення знань і отримання практичних навичок отримання мінімальних аналітичних форм представлення перемикальних функцій; побудови комбінаційних схем для їх реалізації в заданому елементному базисі.
Теоретичні відомості.
Змінну із скінченним числом значень (станів) називають перемикальною, а з двома значеннями – булевою.
Функція, яка має, як і кожна її змінна, скінченне число значень, називається перемикальною (логічною).
Логічна функція, число можливих значень якої та кожної її незалежної змінної дорівнює двом, є булевою. Таким чином, булева функція – це окремий випадок перемикальної.
Операція – це чітко визначена дія над одним або кількома операндами, яка створює новий об’єкт (результат).
Позначення операції
Читається
Назва операції
¬
НЕ
Заперечення (інверсія)
∧
І
Кон'юнкція (логічне множення)
∨
АБО
Диз'юнкція (логічне додавання)
Основними булевими операціями є заперечення (операція НЕ, інверсія), диз’юнкція (операція АБО, логічне додавання, об’єднання) і кон’юнкція (операція І, логічне множення).
Заперечення – це одномісна булева операція / (читається “не х”), результатом якої є значення, протилежне значенню операнда.
Диз’юнкція – це булева операція / (читається x1 або x2), результатом якої є значення нуль тоді і тільки тоді, коли обидва операнди мають значення нуль.
Кон’юнкція – це булева операція / (читається x1 і x2), результатом якої є значення одиниці тоді і тільки тоді, коли значення кожного операнда дорівнює одиниці у виразі /.
Операції заперечення, диз’юнкції і кон’юнкції можна задати за допомогою таблиць істинності, в яких зліва подані значення операндів, а справа – значення булевої функції.
Таблиця істинності - це прямокутна таблиця, що виражає відповідність між усіма наборами величин змінних і величин функції. У такій таблиці, як усталено для двозначної логіки, 1 позначає істинність, 0 позначає хибність. У даній таблиці істинності подано два аргумента (А та В) та результати булевих операцій.
/
Мінімізація булевих функцій за методом Квайна-Мак-Класки.
Метод Квайна-Мак-Класки заснований на кубічному поданні термів ДНФ із попередньою розбивкою кубів на підгрупи, обумовлені однаковим числом одиниць. Розбивка дає можливість порівнювати куби тільки за сусідніми за числом одиниць групами для зменшення кількості переборів.
В ітеративній процедурі мінімізації попарне порівняння можна виконувати тільки між сусідніми групами.
Вихідне завдання функції визначається для зручності десятковими кодами двійкових кубів, що відповідають ДНФ.
Знаходження первинних імплікант на першому етапі можна спростити за допомогою числового зображення булевих функцій, а саме:
1. Всі вихідні терми записуються у вигляді їхніх двійкових номерів.
2. Всі номери розбиваються на непересічні групи за числом одиниць. Умовою склеювання й утворення нового терму є наявність розбіжності в підгрупах тільки за однією координатою в одному двійковому розряді й наявність спільних незалежних координат.
3. В i-групу включають всі номери наборів, що мають у своєму записі i одиниць.
4. Попарне порівняння виконується тільки між сусідніми за номером групами. Групи, які розрізняються за двома розрядами і більше, не має сенсу порівнювати.
Мінімізація булевих функцій за методом карт Карно.
Для мінімізації функцій із кількістю букв 6≤n застосовують карти Карно. Їх будують у вигляді таблиць з 2n кліток із розмічуванням рядків і стовпчиків змінними.
Мінтерми в сусідніх клітинках карти Карно в рядку (з урахуванням верхніх і нижніх) або стовпчику (з урахуванням крайніх) розрізняють за значеннями однієї змінної, що дає змогу виконувати операцію склеювання за цією змінною.
Загальні правила мінімізації:
1) зображають карту Карно для n змінних і розмічують її рядки і стовпчики. У к...